package backtracing;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 业务开发中可能涉及凑整问题
 * 列如需要为用户推荐电源设备，可以任意组合，要求必须达到或等于指定容量或价格，求出所有组合，然后再根据业务需求进一步推荐
 */
public class BackTracingCombinationSum {
    /**
     * <a href="https://leetcode.cn/problems/combination-sum/">组合总和</a>
     */
    public static class SolutionCombinationSum {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<List<Integer>> result = new ArrayList<>();
            backtracing(candidates, target, 0, result, new ArrayList<>());
            return result;
        }

        public static void backtracing(int[] candidates, int target, int index, List<List<Integer>> result, List<Integer> combine) {
            if (target == 0) {
                result.add(new ArrayList<Integer>(combine));
                return;
            }

            for (int i = index; i < candidates.length; i++) {
                // candidates是有序的，若选择i索引的值已经超过目标值，继续遍历没意义
                if (target - candidates[i] < 0) {
                    break;
                }

                // 在第i次回溯，选择一个元素
                combine.add(candidates[i]);
                // “组合总和”允许多次选择同一个位置的元素，因此下一次仍然尝试从i位置开始
                backtracing(candidates, target - candidates[i], i, result, combine);

                // 第i+1次枚举结束，进行回溯
                combine.remove(combine.size() - 1);
            }
        }
    }

    /**
     * <a href="https://leetcode.cn/problems/combination-sum-ii/">组合总和 II</a>
     */
    public static class SolutionCombinationSumII {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<List<Integer>> result = new ArrayList<>();
            backtracing(candidates, target, 0, result, new ArrayList<>());
            return result;
        }

        public static void backtracing(int[] candidates, int target, int index, List<List<Integer>> result, List<Integer> combine) {
            if (target == 0) {
                result.add(new ArrayList<Integer>(combine));
                return;
            }

            for (int i = index; i < candidates.length; i++) {
                // candidates是有序的，若选择i索引的值已经超过目标值，继续遍历没意义
                if (target - candidates[i] < 0) {
                    break;
                }

                // 如果i>index说明正处于第i次回溯的第i+1个元素选择
                // 题目要求不能重复，由于数组排序了，因此直接与上一个已选择的元素进行比较去重即可
                if (i > index && candidates[i] == candidates[i - 1]) {
                    continue;
                }

                // 在第i次回溯，选择一个元素
                combine.add(candidates[i]);
                // “组合总和 II”要求同一个位置的元素不能选择多次，因此在下一轮枚举中排除当前项，即下一轮从i+1开始枚举
                backtracing(candidates, target - candidates[i], i + 1, result, combine);

                // 第i+1次枚举结束，进行回溯
                combine.remove(combine.size() - 1);
            }
        }
    }
}
